1. Technical Field
The present invention relates generally to an improved data processing system and in particular to a method and apparatus for determining edge directions in a directed graph. Still more particularly, the present invention provides a method and apparatus for identifying an edge to be inverted for minimizing upward directed edges in a cyclic compound directed graph.
2. Description of Related Art
A directed graph is a graph having nodes with one way edges interconnecting graph nodes. A directed graph may by cyclic or acyclic. An acyclic directed graph does not contain any cycles. That is, if there is a path, i.e., one or more edges, or arcs, from a first node to a second node, there is no combination of edges that provide a return path from the second node to the first node. A cyclic graph, on the other hand, contains at least one cycle.
A compound directed graph is a directed graph having one or more nodes referred to as subgraph, or compound, nodes that contain one or more nodes. Many uses of compound directed graphs exist. For example, compound directed graphs are often employed for business process modeling, graphic display of hierarchical systems, and the like. To facilitate readability of a compound directed graph, it is desirable for a compound directed graph to generally flow from top-to-bottom. That is, it is desirable to minimize the number of upward edges in a compound directed graph.
Various software applications for generating compound directed graphs exist. These software applications use algorithms that identify a feedback arc set, that is edges. Solution of a feedback arc set is nondeterministic polynomial (NP), and thus the computational complexity grows very fast relative to the input data size. However, conventional graphing algorithms are unable to effectively minimize the number of upward flowing edges when drawing a cyclic compound directed graph. Accordingly, compound directed graphs plotted by graphing applications often have numerous edges that flow against one another. Accordingly, the readability and general aesthetics of a compound directed graph are typically undesirable when a compound directed graph is plotted by conventional graphing applications. Additionally, existing graphing applications tend to minimize the vertical length of subgraphs at the expense of requiring additional upward edges.
It would be advantageous to provide a graphing application that determines vertical directions of edges for reducing the number of upward directed edges in a cyclic compound directed graph. It would be further advantageous to provide a graphing application that identifies one or more edges for inversion by a polynomial algorithm such that a near-optimum reduction in the number of upward directed edges in a compound directed graph is obtained.